"""
Problem 25: https://projecteuler.net/problem=25

The Fibonacci sequence is defined by the recurrence relation:

    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

    F1 = 1
    F2 = 1
    F3 = 2
    F4 = 3
    F5 = 5
    F6 = 8
    F7 = 13
    F8 = 21
    F9 = 34
    F10 = 55
    F11 = 89
    F12 = 144

The 12th term, F12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000
digits?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/10
'''

def solution(b: int = 1000) -> int :
    '''
    
    any b(>=1), exist i, F(i-1) < 10**b <= F(i)
    
    >>> print(solution(2))
    7
    >>> print(solution(3))
    12
    '''
    
    maxNum = 10**(b-1)
    a,b = 1,1
    i = 2
    
    while b < maxNum:
        b, a = (a+b), b
        i += 1
    
    return i

    

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(solution())
    # 4782

    
    
    
    


    


